package com.hzmg.algorithm;

import com.google.common.base.Stopwatch;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Supplier;

/**
 * 混合排序尝试:
 * 元素少时使用插入排序，数量多时使用快速排序。
 * 以快排为主，递归深度大了转堆排，快排序好了结合插排。
 * 快速排序（大于1000）->插入排序(小于等于1000)-转为希尔排序-插入时有序区使用二分查找。
 * 插入排序不适合对于数据量比较大的排序应用。量级小于千，插入排序是一个不错的选择：改进方向 对有序区的查找使用二分法，以及希尔排序 希尔排序的实质就是分组插入排序，该方法又称递减增量排序算法
 * 在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。
 *
 * @author zbw
 * @since 2022/9/26
 */
public class MixSort {
    private static final int SHELL_TAG=400;
    public static void main(String[] args) {
        //int[] firstInt = {3, 1, 2, 5, 4, 9, 8, 11};
        int[] firstInt = {3, 1,0,54,654,156,156,1,65144,4,41,864,864,15,6,165,15,25,6156418,948,96,54,18,59,489,48,541,2651,859,4895,415,964,59485,945,9641,65416,545616,54,654156,41425,648964,8964894,564,65456,416,541549,654569,874,874,8965,465,4586,456,4159489,4,548,5,94,8915,61,6545,4654,15896,44654,545,61,654,894,841,561,561,1,541,58,48,4896,489,784,65,165,4894,1,6514,8948,15,489,4,16,1651,654,84, 2, 48,21,1651,561,65156,1651,651,5616,15,448,415,1,4784,1,615,6489,4,414,11,541894,8151,89481,8481,514,84189,489,489,489,48941,51,5, 4, 9, 8, 11};
        int[] secondInt = {3, 1,0,54,654,156,156,1,65144,4,41,864,864,15,6,165,15,25,6156418,948,96,54,18,59,489,48,541,2651,859,4895,415,964,59485,945,9641,65416,545616,54,654156,41425,648964,8964894,564,65456,416,541549,654569,874,874,8965,465,4586,456,4159489,4,548,5,94,8915,61,6545,4654,15896,44654,545,61,654,894,841,561,561,1,541,58,48,4896,489,784,65,165,4894,1,6514,8948,15,489,4,16,1651,654,84, 2, 48,21,1651,561,65156,1651,651,5616,15,448,415,1,4784,1,615,6489,4,414,11,541894,8151,89481,8481,514,84189,489,489,489,48941,51,5, 4, 9, 8, 11};
        int[] thirdInt = {3, 1,0,54,654,156,156,1,65144,4,41,864,864,15,6,165,15,25,6156418,948,96,54,18,59,489,48,541,2651,859,4895,415,964,59485,945,9641,65416,545616,54,654156,41425,648964,8964894,564,65456,416,541549,654569,874,874,8965,465,4586,456,4159489,4,548,5,94,8915,61,6545,4654,15896,44654,545,61,654,894,841,561,561,1,541,58,48,4896,489,784,65,165,4894,1,6514,8948,15,489,4,16,1651,654,84, 2, 48,21,1651};
        int[] forthInt = {3, 1,0,54,654,156,156,1,65144,4,41,864,864,15,6,165,15,25,6156418,948,96,54,18,59,489,48,541,2651,859,4895,415,964,59485,945,9641,65416,545616,54,654156,41425,648964,8964894,564,65456,416,541549,654569,874,874,8965,465,4586,456,4159489,4,548,5,94,8915,61,6545,4654,15896,44654,545,61,654,894,841,561,561,1,541,58,48,4896,489,784,65,165,4894,1,6514,8948,15,489,4,16,1651,654,84, 2, 48,21,1651};
        int[] fifthInt=generateArray(500,100000);
        int[] sixInt=generateArray(500,100000);
        int[] sevenInt=generateArray(5000,100000);
        int[] eightInt=generateArray(5000,100000);
        int[] ninthInt=generateArray(50000,100000);
        int[] tenInt=generateArray(50000,100000);
        int[] elevenInt=generateArray(500000,1000000);
        int[] twelveInt=generateArray(500000,1000000);
        //sort(firstInt);
        //shellSort(firstInt);
        //shell_sort(firstInt);
        //testSort(secondInt);

        /*System.out.println("[firstInt]"+firstInt.length);
        System.out.println("[thirdInt]"+thirdInt.length);*/
        //shell_sort(firstInt);
        //performer(()->quickSortRecursive(secondInt,0,secondInt.length-1));
        //shell_sort(thirdInt);
/*        //希尔排序速度测试：
        shell_sort(firstInt);
        shell_sort(thirdInt);
        shell_sort(fifthInt);
        shell_sort(sevenInt);
        shell_sort(ninthInt);
        shell_sort(elevenInt);*/
        //三值取中快速排序：
/*        performer(()->quickSortRecursive(firstInt,0,firstInt.length-1),"quickSortRecursive");
        performer(()->quickSortRecursive(thirdInt,0,thirdInt.length-1),"quickSortRecursive");
        performer(()->quickSortRecursive(fifthInt,0,fifthInt.length-1),"quickSortRecursive");
        performer(()->quickSortRecursive(sevenInt,0,sevenInt.length-1),"quickSortRecursive");
        performer(()->quickSortRecursive(ninthInt,0,ninthInt.length-1),"quickSortRecursive");
        performer(()->quickSortRecursive(elevenInt,0,elevenInt.length-1),"quickSortRecursive");*/
        //三值取中快速排序结合希尔排序：
        performer(()->quickSortWithShell(secondInt,0,secondInt.length-1),"quickSortWithShell");
        performer(()->quickSortWithShell(forthInt,0,forthInt.length-1),"quickSortWithShell");
        performer(()->quickSortWithShell(sixInt,0,sixInt.length-1),"quickSortWithShell");
        performer(()->quickSortWithShell(eightInt,0,eightInt.length-1),"quickSortWithShell");
        performer(()->quickSortWithShell(tenInt,0,tenInt.length-1),"quickSortWithShell");
        performer(()->quickSortWithShell(twelveInt,0,twelveInt.length-1),"quickSortWithShell");
/*        //对比组：jdk自带Arrays.sort
        arraysSort(firstInt);
        arraysSort(thirdInt);
        arraysSort(fifthInt);
        arraysSort(sevenInt);
        arraysSort(ninthInt);
        arraysSort(elevenInt);*/

    }

    /**
     * first sort
     * 思考：如果取基准用随机数会不会比三分取基更合理点呢。
     * 随机取三个数，用中间的数作为基准
     * 思考：能不能在选择了基准之后，将数直接通过插入放到两边呢
     */
    public static void sort(int[] firstInt) {
        if (firstInt.length < 1000) {

        }
        int pivot = getPivot(firstInt,0,firstInt.length-1);
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        for (int j : firstInt) {
            if (j <= pivot) {
                left.add(j);
            } else {
                right.add(j);
            }
        }
    }

    /*public static int[] shell_sort(int[] array){
        int[] gap=
        int i,j,len=array.length;
        int temp;

    }*/
    public static void arraysSort(int[] firstInt){
        //计时 up:微秒
        Stopwatch stopwatch = Stopwatch.createStarted();
        Arrays.sort(firstInt);
    /*    if (firstInt.length<=10000) {
            System.out.println(Arrays.toString(firstInt));
        }*/
        System.out.println("[arraysSort] using time: " + stopwatch);
    }
    public static void shellSort(int[] a) {
        //计时 up:微秒
        Stopwatch stopwatch = Stopwatch.createStarted();
        int n = a.length;

        int j;
        for (int d = n / 2; d > 0; d /= 2) {/* 希尔增量序列 */
            /* 插入排序 */
            for (int p = d; p < n; p++) {
                int temp = a[p];
                for (j = p; j >= d && a[j - d] > temp; j = j - d) {
                    a[j] = a[j - d];
                }
                a[j] = temp;
            }
        }
        System.out.println(Arrays.toString(a));
        System.out.println("[shellSort] using time: " + stopwatch);
    }

    /**
     * 目前第二快
     * 希尔排序
     * @param arr
     */
    public static void shell_sort(int[] arr) {
        //计时
        Stopwatch stopwatch = Stopwatch.createStarted();
        int gap = 1, i, j, len = arr.length;
        int temp;
        while (gap < len / 3) {
            gap = gap * 3 + 1;
        }
        for (; gap > 0; gap /= 3) {
            for (i = gap; i < len; i++) {
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
        }
        /*if (arr.length<=10000) {
            System.out.println(Arrays.toString(arr));
        }*/
        System.out.println("[shell_sort]using time: " + stopwatch);
    }
    /**
     * 对指定区域进行希尔排序
     */
    public static void shellSort(int[] arr,int start,int end) {

        int gap = 1, i, j, len = end-start;
        int temp;
        while (gap < len / 3) {
            gap = gap * 3 + 1;
        }
        for (; gap > 0; gap /= 3) {
            for (i = start+gap; i < len; i++) {
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
        }
    }
    /**
     * 将每个步长的值先进行排序，内部用二分
     * 事实证明不太行，越优化越差，可能思路本来就不对
     * @param array
     */
    public static void testSort(int[] array){
        //计时
        Stopwatch stopwatch = Stopwatch.createStarted();
        int gap = 1, i, len = array.length;
        int temp;
        while (gap < len / 3) {
            gap = gap * 3 + 1;
        }
        for (; gap > 0; gap /= 3) {
            for (i = 0; i < len; i+=gap) {
                int left,right,middle;
                for(int h=i+gap;h<len;h+=gap){
                    temp=array[h];
                    left=i;
                    right=h-gap;
                    while (left<=right){
                        middle=left+(right-left)/2;
                        if (array[middle]>temp){
                            right=middle-1;
                        }else {
                            left=middle+1;
                        }
                    }
                     for (int j=h-gap;j>=left;j-=gap){
                         array[j+gap]=array[j];
                     }
                     array[left]=temp;

                   /* for (j=h-gap;j>=0;j-=gap){
                        if (temp<array[j]){
                            array[j+gap]=array[j];
                        }else {
                            break;
                        }
                        array[j+gap]=temp;
                    }*/
                }
            }
        }
        if (array.length<=10000) {
            System.out.println(Arrays.toString(array));
        }
        System.out.println("[test_sort]using time: " + stopwatch);
    }

    /**
     * 目前最快
     * 快速排序-递归
     * 使用三者取中划分方式
     * @param array
     */
    public static void quickSortRecursive(int[] array,int start,int end){

        if(start>=end){
            return;
        }
        if(end-start<=1){
            return;
        }
        int mid=getPivot(array,start,end);
        int left=start,right=end;
        while (left<right){
            //遍历查找比mid大的下标
            while(array[left]<=array[mid]&&left<right){
                left++;
            }
            while (array[right]>=array[mid]&&left<right){
                right--;
            }
            swap(array,left,right);
        }
        if (array[left]>=array[mid]){
            swap(array,left,mid);
        }
        //递归调用
        quickSortRecursive(array,start,mid);
        quickSortRecursive(array,mid+1,end);
    }
    /**
     * 快速排序-递归->小于100转为希尔排序
     * @param array
     */
    public static void quickSortWithShell(int[] array,int start,int end){

        if(start>=end){
            return;
        }
        if(end-start<=1){
            return;
        }
        if (end-start<=SHELL_TAG){
            shellSort(array,start,end);
            return;
        }
        int mid=getPivot(array,start,end);
        int left=start,right=end;
        while (left<right){
            //遍历查找比mid大的下标
            while(array[left]<=array[mid]&&left<right){
                left++;
            }
            while (array[right]>=array[mid]&&left<right){
                right--;
            }
            swap(array,left,right);
        }
        if (array[left]>=array[mid]){
            swap(array,left,mid);
        }
        //递归调用
        quickSortWithShell(array,start,mid);
        quickSortWithShell(array,mid+1,end);
    }
    /**
     * 套壳
     * @param supplier
     */
    public static void performer(Meaningless supplier,String name){
        //计时
        Stopwatch stopwatch = Stopwatch.createStarted();
        try {
            supplier.m();
        } catch (Exception e) {
            e.printStackTrace();
        }
        System.out.println("["+name+"]using time: " + stopwatch);
    }
    public static void swap(int[] array,int left,int right){
        int temp=array[left];
        array[left]=array[right];
        array[right]=temp;
    }
    /**
     * 随机生成数组
     * @param len
     * @param max
     * @return
     */
    public static int[]  generateArray(int len,int max){
        int[] arr=new int[len];
        for(int i=0;i<arr.length;i++){
            arr[i]=(int)(Math.random()*max);
        }
        return arr;
    }

    /**
     * 思考：既然这个值任意的都行，是否可以选出三个然后计算他的平均值来当做Pivot（中心点）呢。
     * 值得一试 TODO：选出三个取平均值做为中心点
     * 随机数的生成本身就是一种代价
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int getPivot(int[] array,int start,int end) {
        int mid=start+(end-start)/2;
        int first = array[start];
        int second = array[mid];
        int third = array[end];
        int select = (first >= second && second >= third) || (third >= second && second >= first) ? 1 : 0;
        if (select == 1) {
            return mid;
        }
        select = (first >= third && third >= second) || (second >= third && third >= first) ? 2 : 0;
        if (select == 2) {
            swap(array,mid,end);
            return mid;
        }
        swap(array,start,mid);
        return mid;
    }
    @FunctionalInterface
    public interface Meaningless {
        void m() throws Exception;
    }

    /**
     * 归并排序-迭代版
     */
    public static void mergeSort(int[] array){
        int len = array.length;
        int[] result = new int[len];
        int block, start;

        // 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
        for(block = 1; block < len*2; block *= 2) {
            for(start = 0; start <len; start += 2 * block) {
                int low = start;
                int mid = (start + block) < len ? (start + block) : len;
                int high = (start + 2 * block) < len ? (start + 2 * block) : len;
                //两个块的起始下标及结束下标
                int start1 = low, end1 = mid;
                int start2 = mid, end2 = high;
                //开始对两个block进行归并排序
                while (start1 < end1 && start2 < end2) {
                    result[low++] = array[start1] < array[start2] ? array[start1++] : array[start2++];
                }
                while(start1 < end1) {
                    result[low++] = array[start1++];
                }
                while(start2 < end2) {
                    result[low++] = array[start2++];
                }
            }
            int[] temp = array;
            array = result;
            result = temp;
        }
        result = array;
    }
    /**
     * 归并排序-递归版
     */
    public static void mergeSortRecursive(int[] array,int[] result,int start,int end){
        if (start>=end){
            return;
        }
        int len=end-start,mid=(len>>1+start)
    }
}
